package org.hot100.h240;

/**
 * @Author: wjy
 * @Date: 2022/2/22 16:57
 */
public class Solution {

    public static void main(String[] args) {

//        int[][] ints = {
//                {1, 4, 7, 11, 15},
//                {2, 5, 8, 12, 19},
//                {3, 6, 9, 16, 22},
//                {10, 13, 14, 17, 24},
//                {18, 21, 23, 26, 30}
//        };

//        int[][] ints = {
//                {1, 1}
//        };

        int[][] ints = {
                {0, 0, 0},
                {2, 7, 9},
                {7, 8, 11}
        };

        Solution solution = new Solution();
        System.out.println(solution.searchMatrix3(ints, 7));

    }

    /**
     * 执行用时：10 ms, 在所有 Java 提交中击败了13.55%的用户
     * 内存消耗：47.1 MB, 在所有 Java 提交中击败了19.03%的用户
     * 通过测试用例：129 / 129
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }

        int line = matrix.length, row = matrix[0].length;

        //
        for (int i = 0; i < matrix.length; i++) {
            if (target < matrix[i][0]) {
                line = i;
                break;
            }
        }

        //
        for (int i = 0; i < matrix[0].length; i++) {
            if (target < matrix[0][i]) {
                row = i;
                break;
            }
        }

        for (int i = 0; i < line; i++) {
            for (int j = 0; j < row; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }

        return false;

    }

    /**
     * 执行用时：7 ms, 在所有 Java 提交中击败了20.64%的用户
     * 内存消耗：47.2 MB, 在所有 Java 提交中击败了14.57%的用户
     * 通过测试用例：129 / 129
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }

        int line = 0, row = matrix[0].length - 1;
        return recursion(matrix, target, line, row);
    }


    public boolean recursion(int[][] matrix, int target, int line, int row) {
        if (line >= matrix.length || row < 0 || matrix[line][row] == 'a') {
            return false;
        }
        if (matrix[line][row] == target) {
            return true;
        }
        matrix[line][row] = 'a';
        return recursion(matrix, target, line, row - 1) || recursion(matrix, target, line + 1, row);
    }

    /**
     * 执行用时：5 ms, 在所有 Java 提交中击败了94.46%的用户
     * 内存消耗：46.9 MB, 在所有 Java 提交中击败了23.29%的用户
     * 通过测试用例：129 / 129
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix3(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int row = 0;
        int col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (target > matrix[row][col]) {
                row++;
            } else if (target < matrix[row][col]) {
                col--;
            } else {
                return true;
            }
        }
        return false;
    }

}
